1. Field of the Invention
The present invention relates to a Viterbi decoder of a digital communication system, and more particularly to a Viterbi decoder for decoding symbol data of various code rates according to puncturing patterns.
2. Description of the Prior Art
In general, a Viterbi algorithm is most widely used as a practical and efficient technique for maximum-likelihood decoding of convolutional codes. The maximum-likelihood decoding is used to determine the shortest path through a topological structure called code trellis.
The Viterbi decoding algorithm uses the trellis structure of code and determines the maximum-likelihood estimate of the sequence to be transmitted that has the largest metric. The Viterbi algorithm simply finds a path, a survivor path, which is defined as the most probable path that has the largest accumulated metric through the trellis, in such a way that it processes the received word in an iterative manner. At each step, it compares the metric of all paths entering each state, stores only the survivor with the largest accumulated metric, and discards the unlikely paths at each state.
FIG. 1 shows a block diagram of a conventional Viterbi decoder. The conventional Viterbi decoder comprises a branch metric calculation unit 11, an add/ comparison/ selection unit 12, a path metric network 13, and a survivor memory unit 14.
The branch metric calculation unit 11 receives symbols from a transmission end and calculates metrics BM at each branch. To find an optimum path of the highest statistical probability, the branch metric becomes a hamming distance for a hard decision decoding, whereas it becomes an Euclidean distance for a soft decision decoding. The add/ comparison/ selection unit 12 processes the candidate paths by adding branch metrics obtained from the branch metric calculation unit 11 to the previous path metrics from the path metric network 13, and selects the shortest path by comparing the candidate path metrics. The shortest path is characterized as the survivor path. A survivor path metric SM is supplied to the path metric network 13, and an information for tracing back the survivor path, that is, a decision vector DV is also supplied to the survivor memory unit 14. The survivor memory unit 14 outputs a final decoded symbol through utilization of the decision vector DV.
FIG. 2 shows a diagram illustrating a trace back algorithm of the survivor memory unit 14 in the conventional Viterbi decoder of FIG. 1. When a convolution encoder having a code rate 1/2 operates at a shift register of V stages (the number of state is 2.sup.v =N), the state is represented by contents of the shift register such as b.sub.V-1 b.sub.V-2 . . . b.sub.1 b.sub.0, indicated in the diagram, in binary digits. Here, the encoded message bits are inputted from the left end of the shift register. As shown in FIG. 2, each state has the decision vectors DV of 1 bit, respectively. The previous state is determined by the decision vector DV of the current state. For example, if the trace back is performed at an arbitrary state "b.sub.V-1 b.sub.V-2 . . . b.sub.1 b.sub.0 " selected from the memory storing the current state Vi, then the previous state Vi-1 becomes "b.sub.V-2 . . . b.sub.1 b.sub.0 0" by selecting an upper path when the decision vector DV of the state "b.sub.V-1 b.sub.V-2 . . . b.sub.1 b.sub.0 " is "0", whereas the previous state Vi-1 becomes "b.sub.V-2 . . . b.sub.1 b.sub.0 1" by selecting a lower path when the decision vector DV of the state "b.sub.V-1 b.sub.V-2 . . . b.sub.1 b.sub.0 " is "0". Here, the decision vectors DV of each state is the least significant bit (LSB) of the state corresponding to the survivor path selected in the add/ comparison/ selection unit 12.
Accordingly, since a bit stream of the decision vector DV obtained from the trace back processing corresponds to the right end bit of the shift register of V stages at each encoding cycle, shown in FIG. 2, the bit stream of the decision vector DV corresponds to a message bit inputted in the shift register of the convolution encoder.
FIG. 3 shows a view illustrating a method for determining a decoding depth during the trace back process of the survivor memory unit 14. A survivor path at each state is characterized as a path obtained by trace back from an arbitrary current state to infinity. The survivor path may be the path closest to an encoding path of the encoder. For N states, the optimum process for determining the survivor path finds the closest path among N paths obtained by tracing back of N current states to the infinity.
However, in the Viterbi algorithm, after tracing back to four or five times of constraint length rather than tracing back to the infinity, the result from the trace back in the next is determined as decoded symbol. A progress depth of the trace back is determined as a decoding depth. Additionally, as shown in FIG. 3, since the survivor paths of each state merge into one state during the trace back when the decoding depth of each state is reached, trace back ends at the decoding depth from an arbitrary state.
At this time, it is required that the accurate decoding depth is determined for the convolutional codes of the specific code rates with specific code rates. More particularly, the survivor memory unit 14 processes a trace back algorithm for tracing the previous state corresponding to a decoding depth by using the decision vector DV obtained from the add/ comparison/ selection unit 12. Accordingly, the survivor memory unit 14 requires a memory to store the decision vector DV, as well as number of corresponding decoding depths, and a memory for storing each state.
In digital communication system, the punctured code of high code rate is used to correct error in the channel and increase the efficiency of transmission. In the punctured code, according to special patterns, some symbols has been periodically deleted from output symbols from an encoder having the low code rate so as to obtain a high code rate. Since the punctured code of higher code rate has a characteristic of a high transmission rate, it is widely used in various digital transmission systems.
A punctured convolutional code proposed by Cain, Clark, and Geist in 1979 has been used in the digital communication systems of European or American HDTV and satellite broadcasting services. The European Digital Video Broadcasting system transmits punctured codes with high code rates of 2/3, 3/4, 5/6, 7/8, etc. which is obtained according to the puncturing patterns from the code rate 1/2 in the encoder. Since the codes are depunctured at the receiving end, and the depunctured codes are decoded by the Viterbi decoder, the conventional Viterbi decoder of basic code rate 1/2 can be used.
However, when the Viterbi decoding is performed by the conventional Viterbi decoder, for the punctured codes (for example, code rates 2/3, 3/4, 5/6, 7/8, etc.), the longer decoding depth than for the non-punctured cod (for example, code rate 1/2) is needed to obtain a low bit error rate. Namely, the decoding depth is determined according to the code rates of the punctured codes, and it increases proportionally by the code rate. In the European Digital Video Broadcasting Standard, since the various punctured convolutional codes (code rates 2/3, 3/4, 5/6, 7/8, etc.) are used, it has been known through the simulation that the decoding depth for supporting all of the code rates should be about 96.
Accordingly, since the decoding depth of the Viterbi decoder for decoding depunctured code increases in proportion to the code rate, the survivor memory increases and the processing time is delayed.